相关链接
题目传送门:http://codeforces.com/contest/559/problem/E
官方题解:http://codeforces.com/blog/entry/19237
中文题面:http://blog.csdn.net/mengzhengnan/article/details/47057557
解题报告
这题官方题解是$O(n^4)$的
然而评论区给出了$O(n^3)$甚至$O(n^2)$的算法
不过评论区并没有给题解,只是扔了两份非常不可读的代码
于是我一个都没有懂 QwQ
后来自己想了一个$O(n^3)$的DP,来说一说吧!
考虑最常规的$DP$式子$f[i][j]$表示用了前$i$个路灯,已被照亮的区间的最右端点为$j$
这样的话,只有一种情况会出现问题:
ps:红色的部分会被漏掉
于是我们就预处理出所有路灯向左照的时候覆盖情况
因为超过第i个路灯的位置并且对答案有贡献的路灯最多一个
所以我们就可以枚举是那个路灯超过了i
这样的话,新增转移多了$n^2$个
又因为每一个转移会被使用$O(n)$次,于是总的时间复杂度为:$O(n^3)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 300+9; int n,tot,Hash[N],f[N][N]; struct Mat{int p,l;}m[N]; struct Trans{int l,r,mx;}; vector<Trans> t[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline int Val(int p, int l, int r) { if (r <= p) return 0; if (l >= p) return Hash[r] - Hash[l]; return Hash[r] - Hash[p]; } int main() { n = read(); for (int i=1,p,l;i<=n;i++) { p = read(); l = read(); Hash[++tot] = p; Hash[++tot] = p + l; Hash[++tot] = p - l; m[i] = (Mat){p,l}; } auto cmp = [](const Mat &A, const Mat &B) {return A.p < B.p;}; sort(m+1, m+1+n, cmp); sort(Hash+1, Hash+1+tot); tot = unique(Hash+1, Hash+1+tot) - Hash - 1; for (int i=1,r,l;i<=n;i++) { r = m[i].p; l = m[i].p-m[i].l; for (int j=1,cr,cl;j<i;j++) { if (l > m[j].p) continue; cr = max(r, m[j].p+m[j].l); cl = l; for (int k=j+1;k<i;k++) cl = min(cl, m[k].p-m[k].l); cl = lower_bound(Hash+1, Hash+1+tot, cl) - Hash; cr = lower_bound(Hash+1, Hash+1+tot, cr) - Hash; t[j].push_back((Trans){cl,cr,i}); } l = lower_bound(Hash+1, Hash+1+tot, l) - Hash; r = lower_bound(Hash+1, Hash+1+tot, r) - Hash; t[i].push_back((Trans){l,r,i}); l = m[i].p; r = m[i].p + m[i].l; l = lower_bound(Hash+1, Hash+1+tot, l) - Hash; r = lower_bound(Hash+1, Hash+1+tot, r) - Hash; t[i].push_back((Trans){l,r,i}); } for (int i=1;i<=n;i++) { for (int j=1;j<=tot;j++) f[i][j] = max(f[i][j], f[i-1][j]); for (int k=t[i].size()-1,l,r,mx;~k;k--) { l = t[i][k].l; r = t[i][k].r; mx = t[i][k].mx; for (int j=1;j<=tot;j++) { if (j >= r) break; f[mx+1][r] = max(f[mx+1][r], f[i][j] + Val(j, l, r)); } } } int vout = 0; for (int i=1;i<=n+1;i++) { for (int j=1;j<=tot;j++) { vout = max(vout, f[i][j]); } } printf("%d\n",vout); return 0; }
Great blog! Is your theme custom made or did you download it from somewhere? A theme like yours with a few simple adjustements would really make my blog stand out. Please let me know where you got your theme. Bless you
I like this web blog very much, Its a real nice office to read and obtain information.